package com.github.yangyishe.p100;

/**
 * 67. 二进制求和
 * https://leetcode.cn/problems/add-binary/description/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
 *
 *
 *
 * 示例 1：
 *
 * 输入:a = "11", b = "1"
 * 输出："100"
 * 示例 2：
 *
 * 输入：a = "1010", b = "1011"
 * 输出："10101"
 *
 *
 * 提示：
 *
 * 1 <= a.length, b.length <= 104
 * a 和 b 仅由字符 '0' 或 '1' 组成
 * 字符串如果不是 "0" ，就不含前导零
 */
public class Problem67 {
    public static void main(String[] args) {
        String a="10100000100100110110010000010101111011011001101110111111111101000000101111001110001111100001101";
        String b="110101001011101110001111100110001010100001101011101010000011011011001011101111001100000011011110011";
//        String a="1010";
//        String b="1011";

        Problem67 problem67 = new Problem67();
        String s = problem67.addBinary(a, b);
        System.out.println("s = " + s);
    }

    /**
     *
     * 思路:
     * 不能使用原始数字转字符串,再转回来的思路, 而是均放在字符串中处理
     *
     * @param a
     * @param b
     * @return
     */
    public String addBinary(String a, String b){
        //1. 创建一个预结果集, size=Math.max(a.length,b.length)+1
        char[] charsA = a.toCharArray();
        char[] charsB = b.toCharArray();
        char[] charsR=new char[Math.max(charsA.length,charsB.length)+1];

        //2. 从最后一位开始,向前遍历, 对结果进行累加
        int acc=0;
        for(int i=0;i<charsR.length;i++){
            int iA=charsA.length>i?charsA[charsA.length-1-i]-'0':0;
            int iB=charsB.length>i?charsB[charsB.length-1-i]-'0':0;

            int iR = iA + iB + acc;
            char cR=(char)('0'+ (iR &1));
            acc=iR>>1;

            charsR[charsR.length-1-i]=cR;
        }


        //3. 将结果数组转化为字符串
        int offset=charsR[0]=='0'?1:0;
        return new String(charsR,offset,charsR.length-offset);

    }

    /**
     *
     * ->已废弃. 原因: 没有考虑位数超高的情况
     *
     * 思路:
     * 先将字符串转换为数字
     * 再将数字相加
     * 再将数字转化为字符串
     * @param a
     * @param b
     * @return
     */
    /*public String addBinary(String a, String b) {
        //1. 先将字符串转换为数字
        int ia = str2Num(a);
        int ib = str2Num(b);

        //2. 再将数字相加
        int r=ia+ib;

        //3. 再将数字转化为字符串

        return num2Str(r);
    }

    private int str2Num(String s){
        int result=0;
        for(char c:s.toCharArray()){
            result=(result<<1)+(c-'0');
        }
        return result;
    }

    private String num2Str(int i){
        if(i==0){
            return "0";
        }
        StringBuilder sb=new StringBuilder();
        while(i!=0){
            sb.insert(0,(char)((i&1)+'0'));
            i=i>>1;
        }
        return sb.toString();
    }*/
}
